public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode root;//将来这个引用指向的就是根节点

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //检测值为k的元素是否存在
    public boolean find(TreeNode root,char k){
        if (root == null){
            return false;
        }
        if (root.val == k){
            return true;
        }
        boolean leftVal = find(root.left,k);
        if (leftVal == true){
            return true;
        }
        boolean rightVal = find(root.right,k);
        if (rightVal == true){
            return true;
        }
        return false;
    }


    //判断两颗二叉树是否相同
    public boolean isSameTree(TreeNode q,TreeNode p){
        if (q != null&& p == null||q == null&& p != null){
            return false;
        }
        //两个都为空
        if (p == null&&q == null){
            return true;
        }
        //两个引用都不为空
        if (p.val != q.val){
            return false;
        }
        return isSameTree(q.left,p.left)&&isSameTree(q.right,p.right);
    }

    //是否存在相同的子树
    public boolean isSubTree(TreeNode root,TreeNode subRoot){
        if (root == null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubTree(root.left,subRoot)){
            return true;
        }
        if (isSubTree(root.right,subRoot)){
            return true;
        }
        return false;
    }


    //翻转二叉树
    public TreeNode invertTree(TreeNode root){
        if (root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //判断一棵二叉树是否为平衡二叉树
    public int TreeHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftTree = TreeHeight(root.left);
        int rightTree = TreeHeight(root.right);
        return leftTree>rightTree ? leftTree+1:rightTree+1;
    }
    //大量递归，时间复杂度大
    public boolean isBalancedTree(TreeNode root){
        if (root == null){
            return true;
        }
        int leftTree = TreeHeight(root.left);
        int rightTree = TreeHeight(root.right);
        return Math.abs(leftTree - rightTree) <= 1
                &&isBalancedTree(root.left)
                &&isBalancedTree(root.right);
    }
    //
    public int TreeHeight1(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftTree1 = TreeHeight1(root.left);
        int rightTree1 = TreeHeight1(root.right);
        if (leftTree1 >= 0 && rightTree1 >= 0 &&Math.abs(leftTree1-rightTree1) <= 1){
            return Math.max(leftTree1,rightTree1)+1;
        }else {
            return -1;
        }
    }
    public boolean isBalancedTree1(TreeNode root){
        if (root == null){
            return true;
        }
        return TreeHeight(root)>=0;
    }

    //判断是否为对称二叉树
    public boolean isSymmetric(TreeNode root){
        if (root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if (leftTree == null && rightTree != null||leftTree != null && rightTree == null){
            return false;
        }
        if (leftTree == null&& rightTree == null){
            return true;
        }
        if (leftTree.val != rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
        &&isSymmetricChild(leftTree.right,rightTree.left);
    }
}
